/*空闲块以链表的形式进行管理，每个块包含一个Header大小的头部，以及n*Header大小的空闲空间，malloc函数返回的是空闲空间（不包含头部）
  
  头部包含的信息是指向下一个空闲块的指针ptr，以及一个记录块大小的unsigned数size，也就是说当前块的上一块的ptr，其实是指向当前块的指针
*/
#include <stdio.h>
#include <unistd.h>

#define NALLOC 1024

typedef double Align;//该系统中double为最受限类型

union header {
	struct {
		union header *ptr;
		unsigned size;
	} s;
	Align x;
};//header联合的大小为所占空间最大的成员的大小，即最受限类型的大小

typedef union header Header;

static Header base;//base是整个空闲块链表的头部
static Header *freep = NULL;//freep指向上一次完成操作时的块的上一块

void *malloc(unsigned nbytes);
static Header *moreroce(unsigned nu);
void free(void *ap);

int main(void)
{
	int *p;
	int i;
	if((p = (int *) malloc(100 * sizeof(int))) == NULL)
		return -1;

	for(i = 0; i < 100; i++)
		*(p + i) = (i + 1) * 2;

	for(i = 0; i < 100; i++)
	{
		printf("%d ", *(p + i));
		if(i % 10 == 9)
			putchar('\n');
	}
	free(p);

	if((p = (int *) malloc(100 * sizeof(int))) == NULL)
                return -1;

        for(i = 0; i < 100; i++)
                *(p + i) = (i + 1) * 2;

        for(i = 0; i < 100; i++)
        {
                printf("%d ", *(p + i));
                if(i % 10 == 9)
                        putchar('\n');
        }
        free(p);
	return 0;
}

void *malloc(unsigned nbytes)
{
	Header *p, *prevp;//p指向当前块，prevp指向上一块
	Header *moreroce(unsigned);
	unsigned nunits;//实际所需空间大小，以一个Header大小为单位

	nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
	//以向上舍入（大于等于该数的最小整数）的方式计算实际需求的空间大小，加上一个Header大小是因为C中的除法是采用向下舍入的方式计算结果
	//为了防止nbytes是Header大小的整数倍时，向上舍入所得结果会比预期值大1，因此还需要进行-1操作。商的结果+1表示一个头部

	if((prevp = freep) == NULL)//每次进入malloc函数时，将prevp指向上一次退出函数时返回的块的上一块，如果是第一次进入该函数，那么就为NULL
	{
		base.s.ptr = prevp = freep = &base;//第一次进入函数时设置freep和prevp指向base，同时base的ptr成员指向自身，构成一个闭合的链表
		base.s.size = 0;
	}

	for(p = prevp -> s.ptr; ; prevp = p, p = p -> s.ptr)//更新条件为当前块变成上一块，而当前块的下一块变为当前块
	{
		if(p -> s.size >= nunits)
		{
			if(p -> s.size == nunits)
				prevp -> s.ptr = p -> s.ptr;//让上一块的ptr直接指向当前块的下一块
			else
			{
				p -> s.size -= nunits;//当前块的大小减少units
				p += p -> s.size;//返回当前块的尾部
				p -> s.size = nunits;//标准返回的块的大小
			}
			freep = prevp;//保留返回块的上一块的指针
			return (void *)(p + 1);//只返回当前块的空闲空间，不返回头部
		}
		if(p == freep)//p是从freep所指的块的下一块开始的，如果再次回到freep，说明对整个链表已完成一轮搜寻，没有找到大于等于所需空间的块
			if((p = moreroce(nunits)) == NULL)//调用moreroce函数请求系统分配空间，并让p指向分配的块的上一块
				return NULL;
	}
}

static Header *moreroce(unsigned nu)
{
	char *cp;
	void  *sbrk(int);
	Header *up;

	if(nu < NALLOC)//一次调用至少分配NALLOC个Header大小的空间
		nu = NALLOC;
	cp = sbrk(nu * sizeof(Header));
	
	if(cp == (char *) -1)//sbrk返回-1时，返回NULL
		return NULL;
	up = (Header *) cp;//以Header大小为单位对分配的空间进行处理
	up -> s.size = nu;
	
	free((void *) (up +1));//设置完头部之后，调用free函数将头部后面的空闲空间插入到空闲区域
	return freep;//完成free操作后，freep指向的是分配块的上一块
}

void free(void *ap)
{
	Header *bp, *p;//bp指向待释放块，p指向当前块

	bp = (Header *) ap - 1;//回到块的头部
	
	for(p = freep; !(bp > p && bp < p -> s.ptr); p = p -> s.ptr)//由于块的排列是根据块的地址递增顺序，从freep所指的块开始循环
	//直到待释放块的地址大于当前块并且小于当前块的下一块时退出循环
		if(p >= p -> s.ptr && (bp > p || bp < p -> s.ptr))//还有一种情况是，待释放块的地址大于链表的最后一块，或者小于链表的第一个块
			break;

	if(bp + bp -> s.size == p -> s.ptr)//如果待释放块紧邻当前块的下一块
	{
		bp -> s.ptr = p -> s.ptr -> s.ptr;//将待释放块的ptr指向当前块的下一块的下一块
		bp -> s.size += p -> s.ptr -> s.size;//合并待释放块和当前块的下一块
	}
	else
		bp -> s.ptr = p -> s.ptr;//否则将待释放块的ptr指向当前块的下一块

	if(p + p -> s.size == bp)//如果当前块与待释放块紧邻
	{
		p -> s.ptr = bp -> s.ptr;//将当前块的pr指向待释放块的下一块
		p -> s.size += bp -> s.size;//合并当前块和待释放块
	}
	else
		p -> s.ptr = bp;//否则将当前块的ptr指向待释放块

	//如果待释放与当前块和当前块的下一块都不紧邻，那么就先执行第一个else，再执行第二个else，同时待释放块的size不改变
	//两个if-else语句不能调换顺序

	freep = p;//freep指向当前块
}

/*整个程序最难的就是第一次执行malloc函数时的操作，所以重点解释该部分：

  首先声明一个base，是整个空闲块链表的头部，其成员ptr需要指向空闲块链表的第一个块，而空闲块链表的最后一块成员ptr指向base
  这样就能实现一个闭合的链表。

  首次指向malloc函数时，(prevp = freep) == NULL，将prevp和freep指向base，而base成员ptr指向base，也就是说freep -> s.ptr ==
  prevp -> s.ptr == freep == prevp == &base

  进入到for循环，(p = prevp -> s.ptr) == freep，调用moreroce函数，系统分配一个大于等于NALLOC * sizeof(Header)大小的空间
  并将该空间作为一个块，调用free函数该块的空闲空间插入到空闲区域

  在free函数中，bp指向该块的头部，而p = freep，即p指向的是base，那么p -> s.ptr == &base，也就是说p和p -> s.ptr所指向的地址是一样的，
  即p == p -> s.ptr，并且无论是bp > p或者是bp < p -> s.ptr，必然满足其中的一个条件，因为bp != p, if条件判断为真，跳出循环

  由于p == p -> s.ptr == &base，而base.s.size == 0，并且bp != p，那么两个if-else语句的判断条件都为假，第一个else结果为
  bp -> s.ptr == p -> s.ptr == &base，即bp所指的块的头部成员ptr指向base，第二个else结果为p -> s.ptr == base.s.ptr == bp，
  即base成员ptr指向新分配的块，而freep == p == &base

  moreroce函数将freep返回给malloc函数，(p = moreroce(units)) == freep == &base，循环更新，(prevp = p) == &base，
  (p = p -> s.ptr) == base.s.ptr，即prevp指向base，而p指向第一个块，之后再将所需大小的空闲空间返回给主调函数，同时
  (freep = prevp) == &base，对malloc函数的第一次调用完成
*/


